import java.util.ArrayList;
import java.util.List;

/**
* @description: 周赛312 t3
* @author hewei
* @date 2022/9/25 14:28
* @version 1.0
*/

public class GoodIndices {

    public List<Integer> goodIndices1(int[] nums, int k) {
        int n = nums.length;
        List<Integer> ans = new ArrayList<>();
        if (n <= 2 * k) return ans;
        if (k == 1) {
            for (int i = 1; i < n - 1; i++) {
                ans.add(i);
            }
            return ans;
        }
        boolean[] left = new boolean[n];
        boolean[] right = new boolean[n];
        int l = 0;
        int r = 1;
        while (r < n - k - 1) {
            if (nums[r] > nums[r - 1]) {
                l = r;
            }
            if (r - l + 1 == k) {
                left[r + 1] = true;
                ++l;
            }
            ++r;
        }
        l = n - 2;
        r = n - 1;
        while (l > k) {
            if (nums[l] > nums[l + 1]) {
                r = l;
            }
            if (r - l + 1 == k) {
                right[l - 1] = true;
                --r;
            }
            --l;
        }
        for (int i = 0; i < nums.length; i++) {
            if (left[i] && right[i]) ans.add(i);
        }
        return ans;
    }

    public List<Integer> goodIndices(int[] nums, int k) {
        int n = nums.length;
        List<Integer> ans = new ArrayList<>();
        int[] count = new int[n];
        int temp = 1;
        int last = Integer.MIN_VALUE;
        for (int i = n - 2; i >= 1; i--) {
            if (nums[i + 1] <= last) {
                ++temp;
            } else {
                temp = 1;
            }
            last = nums[i + 1];
            count[i] = temp;
        }
        temp = 1;
        last = Integer.MIN_VALUE;
        for (int i = 1; i < n - k; i++) {
            if (nums[i - 1] <= last) {
                ++temp;
            } else {
                temp = 1;
            }
            last = nums[i - 1];
            if (i >= k && count[i] >= k && temp >= k) ans.add(i);
        }
        return ans;
    }
}